package airthmetic.exercise.backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _17_电话号码的字母组合 {

    public static List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0){
            return new ArrayList<String>();
        }
        List<String> res = new ArrayList();
        Map<Character, char[]> cache = new HashMap();
        cache.put('2',new char[]{'a','b','c'});
        cache.put('3',new char[]{'d','e','f'});
        cache.put('4',new char[]{'g','h','i'});
        cache.put('5',new char[]{'j','k','l'});
        cache.put('6',new char[]{'m','n','o'});
        cache.put('7',new char[]{'p','q','r','s'});
        cache.put('8',new char[]{'t','u','v'});
        cache.put('9',new char[]{'w','x','y','z'});

        StringBuilder sb = new StringBuilder();
        backtrack(digits,0,cache,sb,res);

        return res;
    }

    public static void backtrack(String digits, int index, Map<Character, char[]> cache, StringBuilder sb, List<String> res) {
        // terminal
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }
        // process current logic
        Character c = digits.charAt(index);
        char[] chars = cache.get(c);

        for (int i = 0; i < chars.length; i++) {
            char s = chars[i];
            sb.append(s);
            // drill down
            backtrack(digits, index + 1, cache, sb, res);
            // backtrack
            sb.deleteCharAt(sb.length() - 1);

        }
    }

    public static void main(String[] args) {
        String test = "234";
        List<String> list = letterCombinations(test);
        System.out.println(list);

    }

}
